\section{Implementation}
Our implementation of the heat kernel signature program was written in C$\#$. We settled on this because all of our group members had experience with the language and the Visual Studio development environment. We were also confident that we would be able to find a good amount of libraries and code samples to aid our implementation if necessary.

In this section the individual classes that comprise the program will be discussed individually and their functions made clear. Furthermore, the program's time performance will be discussed to prove its efficiency.

\subsection{MR\_HKSUtility}
The \textit{MR\_HKSUtility} package contains utility classes used by other programs within the program structure. One of the classes in this package is the \textit{OffReader} class, which represents the functionality to generate Laplacian matrices from .off files. It is a fairly simple program. It can read a file in the .off format and store the resulting Laplacian matrix in a .dat file that may in turn be read by the MatLab script. The other class in the \textit{MR\_HKSUtility} package is the \textit{Storage} class. This class can be used by other programs to store file data by serializing it, which makes for more efficient storage, saving and loading.

\subsection{MR\_HKSLaplacian}
The \textit{MR\_HKSLaplacian} package contains one class. This class is \textit{LaplacianSaver}, whose only function is to use the \textit{OffReader} class to save Laplacian matrices for all .off files in the given directory. It has no other functions.

\subsection{MR\_HKSCalc}
The \textit{MR\_HKSCalc} package contains the more complex calculation classes used to generate the feature vectors and distance matrix. The first and most important of these is the \textit{HKSCalculator} class. Its function is to take the .eval and .vect files generated by the MatLab script, use them to calculate the heat kernel signature values and store these in the feature vector file. It can also take these values and generate a distance matrix in .csv file format.

A less important class in this package is the \textit{ComparisonCalculator} class. This class is not essential to the program's function, but is used to make it easier to evaluate its performance. It can be used to extract the distance values for one or more particular models from the complete distance matrix file and put them in order of shortest distance, making it easy to evaluate the algorithm's performance.

\subsection{Performance}
Apart from the main implementation classes, a performance analysis program was created to analyze the results of the main program. This program is stored in a separate solution from the main implementation classes. There are several classes in the \textit{Performance} package. The \textit{Analyzer} class is used to compute the performance of our implementation by using several performance measures. The \textit{Program} class contains the main method used to start the interface and also houses a few utility methods. Finally, the \textit{PerformanceWindow} class uses Windows Forms to visualize the data and take user input.

\subsection{MR\_HKSColorizer}
The \textit{MR\_HKSColorizer} package contains another class that is not part of the HKS implementation itself but can be used for analysis, the \textit{Colorizer} class. Its function is to take an existing .off model and use precomputed eigenvalues and eigenvectors for that model to color it, showing the heat transfered for each vertex at a certain t. This class was not even used in the performance analysis in this report, but only to create some illustrations for the presentation of our implementation. It is included for the sake of completeness.

\subsection{MatLab}
We received permission from the course's instructor to use MatLab for the calculation of the eigenvalues and eigenvectors. The MatLab program consists of a simple script that reads all .dat files in the given directory, calculates the eigenspace for each one, and finally stores the 250 highest eigenvalues and eigenvectors in their own files, using the same file name as the original .dat files, but with .eval and .vect extensions respectively. This is the only part of the project implemented in MatLab.

\subsection{Time Performance}
Concerning the time performance of the program, we can state that our results seem to be fairly good. Generating the Laplacian matrix files takes linear time and is dependent on the size of the model. On the whole it can be considered trivial. The next step is by far the most time-consuming: calculating the eigenspace. We were fortunate to be allowed to use MatLab for this part of the implementation, as it performs far better than the other libraries with which we experimented. For the whole set of 684 models computation takes roughly nine hours using PC with a Core 2 Duo E6750 processor and 4GB of RAM. 

Having computed the eigenvalues and eigenvectors, constructing the feature vectors is next, with 250 eigenvalue/eigenvector pairs and 100 steps per model. Note that at this point the size and complexity of the original model have no influence on computation time anymore. Using a reasonably fast computer the construction of the feature vectors takes roughly 10 minutes.

Finally, there is the construction of the distance matrix. This step, too, is almost trivial, computation-wise, compared to the computation of the eigenspace. Using a reasonably fast computer the computation takes only a second. The program's time performance on the whole can be called satisfactory.
\clearpage 